package leetcode.graph.bfs.p1091;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 
 * @Title: Solution.java 
 * @Package leetcode.graph.bfs.p1091 
 * @Description: 1091. 二进制矩阵中的最短路径
 * @author CandyWall   
 * @date 2021年1月17日 下午2:43:50 
 * @version V1.0
 */
class Solution {
    private int R;
    private int C;

    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid[0][0] == 1) {
            return -1;
        }
        R = grid.length;
        C = grid[0].length;
        if(R == 1 && C == 1) {
            return 1;
        }
        
        // BFS
        boolean[][] visited = new boolean[R][C];
        int[][] distances = new int[R][C];
        int[][] dirs = {{-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}};
        
        Queue<Integer> queue = new LinkedList<>();
        
        queue.add(0);
        visited[0][0] = true;
        distances[0][0] = 1;
        while(!queue.isEmpty()) {
            int v = queue.remove();
            int x = v / C, y = v % C;
            for(int d = 0; d < 8; d++) {
                int nextX = x + dirs[d][0];
                int nextY = y + dirs[d][1];
                if(inArea(nextX, nextY) && !visited[nextX][nextY] && grid[nextX][nextY] == 0) {
                    queue.add(nextX * C + nextY);
                    visited[nextX][nextY] = true;
                    distances[nextX][nextY] = distances[x][y] + 1;
                    if(nextX == R - 1 && nextY == C - 1) {
                        return distances[nextX][nextY];
                    }
                }
            }
        }
        return -1;
    }

    // 判断二维数组的索引是否合法
    private boolean inArea(int x, int y) {
        return x >= 0 && x < R && y >=0 && y < C;
    }
    
    public static void main(String[] args) {
        System.out.println(new Solution().shortestPathBinaryMatrix(new int[][] {{0, 1}, {1, 0}}));
    }
}